home *** CD-ROM | disk | FTP | other *** search
/ MACD 5 / MACD 5.bin / workbench / tools / czesc_2 / makewords / source / dicttotables.c < prev    next >
C/C++ Source or Header  |  1990-08-12  |  9KB  |  328 lines
  1. /* DictToTables.c - convert an ASCII dictionary file into a file of two tables
  2. containing the frequency of occurrence of each trigram in the dictionary.
  3.  
  4. "Words" in the dictionary are groups of 3 to MAXLEN letters.  All other
  5. characters are ignored.   Thus you may use any text file that contains
  6. a variety (the bigger the better) of words.  You could even use a
  7. Latin text to generate frequency tables for Latin.
  8.  
  9. The trigram frequencies are first stored in an array ( nn[][][] ),
  10. then put in the two tables, then the two tables are written to a file.
  11. The file, after compilation, may be linked with Unjumble.o or PhoneWords.o
  12.  
  13. The two tables are a bit table and a nybble table, wherein the frequencies
  14. have been scaled from 'short int' to nybble (4 bits) size.
  15. The bit and nybble tables together allow the trigram frequencies to be
  16. reconstructed.  If the frequency for a trigram is non-zero then the
  17. corresponding bit in the bit table is set.  The frequency for that trigram
  18. is stored as the next nybble in the nybble table.  This strategy requires only
  19. the non-zero frequencies be stored, with the bit table showing the
  20. position of the non-zero trigrams.  With about 4000 non-zero trigrams only
  21. about 4800 bytes are required to store the trigram data.
  22.  
  23. dictionary -> words -> nn[][][] -> bit_table/nybble_table -> file
  24.  
  25.                                 Ron Charlton
  26.                              9002 Balcor Circle
  27.                              Knoxville, TN 37923
  28.    
  29.                              Phone: (615)694-0800
  30.    
  31.                               PLINK: R*CHARLTON
  32.                            BINTNET: charltr@utkvx1
  33.  
  34.                                  05-Jul-90
  35.  
  36. This program is in the public domain and may be used for any purpose.
  37.  
  38. Usage:   1> DictToTables
  39.  
  40. */
  41.  
  42. #include <ctype.h>
  43. #include <stdio.h>
  44. #include <assert.h>
  45.  
  46. #define MAXLEN 15
  47. #define MAXBUCKETS 2000
  48.  
  49. #define TRUE 1
  50. #define FALSE 0
  51.  
  52. #define BIT_TABLE_SIZE (26 * 26 * 26 / 32 + 1)
  53.  
  54. unsigned long bit_table [ BIT_TABLE_SIZE ];    /* the bit table */
  55.  
  56. unsigned long *nybble_table;        /* the nybble table (allocated later) */
  57. int nybble_table_size;
  58.  
  59. unsigned short nn[27][27][27];        /* array of trigram frequencies */
  60. short bucket [ MAXBUCKETS ];
  61. int nonzero;                /* how many trigrams exist */
  62.  
  63. char infile [ 81 ] = "dict.txt";
  64. char outfile [ 81 ] = "tables.c";
  65. char name [ 81 ];
  66. char wordbuf [ 256 ];
  67. FILE *in, *out, *fopen();
  68.  
  69. main()
  70. {
  71. int len;
  72. unsigned long *calloc();
  73.  
  74. printf ("Convert an ASCII dictionary file to one containing two tables\n"
  75.     "encoding trigram weights (frequencies).  The input file should\n"
  76.     "many different words in the desired language.\n\n" );
  77.  
  78. /* get file names and open them */
  79. do_infile();
  80. do_outfile();
  81.  
  82. printf ( "analyzing dictionary...\n" );
  83. /* count trigrams in "words" from infile */
  84. while ( len = getword () )
  85.   if ( len >= 3 && len <= MAXLEN )
  86.     count_trigrams_in_word ( wordbuf );
  87.  
  88. close ( in );
  89.  
  90. printf ( "counting trigrams...\n" );
  91. do_statistics();
  92.  
  93. nybble_table_size = nonzero / 8 + 1;    /* how many longs in table */
  94.  
  95. nybble_table = ( unsigned long *)
  96.         calloc ( (size_t) nybble_table_size,
  97.             (size_t) sizeof ( long )); /* allocate */
  98.  
  99. if ( nybble_table == NULL )
  100.   {
  101.   printf ( "Can't allocate memory for nybble_table.\n" );
  102.   exit ( 20 );
  103.   }
  104.  
  105. printf ( "Building tables...\n" );
  106. build_tables();            /* make bit and nybble tables */
  107.  
  108. printf ( "writing tables to file...\n" );
  109. nybble_table_to_file();        /* store the nybble table */
  110.  
  111. bit_table_to_file();        /* store the bit table */
  112.  
  113. close ( out );
  114.  
  115. print_results();
  116.  
  117. }
  118.  
  119.  
  120. /*--------------------------------------------------------------------*/
  121.  
  122. count_trigrams_in_word ( w )
  123.     /* store count of each trigram in nn[][][] */
  124.     char *w;
  125.     {
  126.     register int len, pos;
  127.     if ( ( len = strlen ( w ) ) >= 3 )
  128.     for ( pos = 0; pos <= len - 3; pos++ )
  129.         ++ nn [ w[pos] - '@' ] [ w[pos+1] - '@' ] [ w[pos+2] - '@' ];
  130.     }
  131.  
  132.  
  133.  
  134. /*--------------------------------------------------------------------*/
  135.  
  136. int getword ()
  137. /* get a word (contiguous group of letters) from infile & make uppercase.
  138. RETURNS - length of word in bytes */
  139. {
  140. register int inword = FALSE, pos = 0, c;
  141.  
  142. while ( ( c = getc ( in ) ) != EOF )
  143.   {
  144.   c = toupper ( c );
  145.   if ( isalpha ( c ) )
  146.     {
  147.     inword = TRUE;
  148.     wordbuf [ pos++ ] = (char) c;
  149.     }
  150.   else if ( inword )
  151.     {
  152.     wordbuf [ pos ] = '\0';
  153.     return ( strlen ( wordbuf ) );
  154.     }
  155.   }
  156.   wordbuf [ pos ] = '\0';
  157.   return ( strlen ( wordbuf ) );
  158. }
  159.  
  160. /*--------------------------------------------------------------------*/
  161.  
  162. do_statistics()
  163.   /* count nonzero trigram values, etc. */
  164.   {
  165.   register int i, j, k;
  166.   
  167.   for ( i = 1; i <= 26; i++ )
  168.     for ( j = 1; j <= 26; j++ )
  169.       for ( k = 1; k <= 26; k++ )
  170.       if ( nn[i][j][k] )        /* filter out zeroes */
  171.         {
  172.         ++nonzero;
  173.         ++bucket [ nn[i][j][k] ];
  174.         }
  175.   
  176.   }
  177.  
  178.  
  179. /*------------------------------------------------------------------------*/
  180.  
  181. print_results()
  182.   /* print results */
  183.   {
  184.   register int i;
  185.   for ( i = 0; i < MAXBUCKETS; i++ )
  186.     if ( bucket [ i ] )
  187.       printf ( "%4d trigrams occurred %4d times\n", bucket [i], i );
  188.  
  189.   printf ( "non-zero trigrams = %d\n", nonzero );
  190.   }
  191.  
  192. /*-----------------------------------------------------------------------*/
  193.  
  194. do_infile()
  195.   {
  196.   printf ( "Enter input file name [%s]: ", infile );
  197.   gets ( name );
  198.   if ( strlen ( name ) > 0 )
  199.     strcpy ( infile, name );
  200.  
  201.   if ( ( in = fopen ( infile, "r" ) ) == NULL )
  202.     {
  203.     printf ( "Can't open %s for input\n", infile );
  204.     exit ( 19 );
  205.     }
  206.   }
  207.  
  208. /*-----------------------------------------------------------------------*/
  209.  
  210. do_outfile()
  211.   {
  212.   printf ( "Enter output file name [%s]: ", outfile );
  213.   gets ( name );
  214.   if ( strlen ( name ) > 0 )
  215.     strcpy ( outfile, name );
  216.  
  217.   if ( ( out = fopen ( outfile, "w" ) ) == NULL )
  218.     {
  219.     printf ( "Can't open %s for output\n", outfile );
  220.     exit ( 20 );
  221.     }
  222.   }
  223.  
  224. /*------------------------------------------------------------------------*/
  225.  
  226. short log2 ( n )
  227.   /* convert short to fit in a nybble by taking log base 2 (truncated): 
  228.     n nonzero - return log base 2 (truncated) of n. 
  229.     n zero      - return 0 */
  230.   unsigned short n;
  231.   {
  232.   register int log = 0;
  233.   while ( n )
  234.     {
  235.     ++log;
  236.     n >>= 1;
  237.     }
  238.   assert ( log < 16 );        /* so as to fit in a nybble */
  239.   return ( log );
  240.   }
  241.  
  242. /*------------------------------------------------------------------------*/
  243.  
  244. build_tables()
  245.   /* use nn[][][] to build the bit and nybble tables */
  246.   {
  247.   register int ptr = 0, i, j, k;
  248.   for ( i = 1; i <= 26; i++ )
  249.     for ( j = 1; j <= 26; j++ )
  250.       for ( k = 1; k <= 26; k++ )
  251.     if ( nn [ i ] [ j ] [ k ] )
  252.       {
  253.       store_nybble ( ptr++, log2 ( nn [ i ] [ j ] [ k ] ) );
  254.       set_bit ( ( i - 1 ) * 26*26  +  ( j - 1 ) * 26  +  ( k - 1 ) );
  255.       }
  256.   }
  257.  
  258. /*------------------------------------------------------------------------*/
  259.  
  260. store_nybble ( nyb_number, value )
  261.   /* put value in nybble pointed to by nyb_number */
  262.   int nyb_number, value;
  263.   {
  264.   int longword, nybble_in_longword;
  265.  
  266.   nybble_in_longword = nyb_number & 7;    /* 3 LSBits pick nybble position */
  267.   longword = nyb_number >> 3;        /* which longword in table */
  268.   assert ( longword < nybble_table_size );
  269.   nybble_table [ longword ] |=
  270.         (long)value << ( nybble_in_longword * 4 ); /* store it */
  271.   }
  272.  
  273. /*------------------------------------------------------------------------*/
  274.  
  275. set_bit ( n )
  276.   /* set bit n in the bit table of 32 bit ints */
  277.   int n;
  278.   {
  279.   int bit, longword;
  280.   longword = n >> 5;                /* which longword in table */
  281.   bit = n & 0x1F;                /* bit 0 - 31 in longword */
  282.   assert ( longword < BIT_TABLE_SIZE );
  283.   assert ( bit < 32 );
  284.   bit_table [ longword ] |= ( 1L << bit );    /* set the bit */
  285.   }
  286.  
  287. /*------------------------------------------------------------------------*/
  288.  
  289. nybble_table_to_file()
  290.     /* store the nybble table in the file */
  291.     {
  292.     int longword;
  293.  
  294.     fprintf ( out, "/* nybble table of trigram frequencies */\n\n" );
  295.     fprintf ( out, "unsigned long nybble_table [] = { 0x%lx\n",
  296.             nybble_table [ 0 ] );
  297.     for ( longword = 1; longword < nybble_table_size; longword++ )
  298.     {
  299.     fprintf ( out, ",0x%lx", nybble_table [ longword ] );
  300.     if ( ( longword % 6 ) == 0 )
  301.         fprintf ( out, "\n" );
  302.     }
  303.     fprintf ( out, "\n\t};\n\n" );
  304.     fprintf ( out, "int nybble_table_size = %d;\n", nybble_table_size );
  305.     }
  306.  
  307. /*--------------------------------------------------------------------*/
  308.  
  309. bit_table_to_file()
  310.     /* store the bit table in the file */
  311.     {
  312.     int longword;
  313.  
  314.     fprintf ( out, "\n\n /* = = = = = = = = = = = = = = = = = = */ \n\n" );
  315.     fprintf ( out, "/* bit table of trigram frequencies */\n\n" );
  316.     fprintf ( out, "unsigned long bit_table [] = { 0x%lx\n", bit_table [ 0 ] );
  317.     for ( longword = 1; longword < BIT_TABLE_SIZE; longword++ )
  318.     {
  319.     fprintf ( out, ",0x%lx", bit_table [ longword ] );
  320.     if ( ( longword % 6 ) == 0 )
  321.         fprintf ( out, "\n" );
  322.     }
  323.     fprintf ( out, "\n\t};\n\n" );
  324.     fprintf ( out, "int bit_table_size = %d;\n", BIT_TABLE_SIZE );
  325.     }
  326.  
  327. /*--------------------------- END OF FILE --------------------------------*/
  328.